package com.demo.jzoffer2;

import com.demo.domain.TreeNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0320_01 {


    /**
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，
     * 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     * <p>
     * 树中节点总数在范围 [0, 5000] 内
     * -1000 <= Node.val <= 1000
     * -1000 <= targetSum <= 1000
     * <p>
     * 解题思路：
     * 本问题是典型的二叉树方案搜索问题，使用回溯法(dfs)解决，其包含先序遍历 + 路径记录两部分
     * 先序遍历：按照 根、左、右 的顺序，遍历数的所有节点
     * <p>
     * 路径记录：再先序遍历中，记录从根节点到当前节点的路径。
     * 当路径为 根节点到叶节点形成的路径 且 各节点值的和等于目标值 sum时，将此路径加入结果列表
     * 题目定义：从树的根节点开始往下一直到 叶节点所经过的节点所形成的一条路径
     * <p>
     * 算法流程：
     * pathSum(root,sum) 函数
     * 初始化：结果列表 res，路径列表 path
     * 返回值：返回 res
     * <p>
     * recur(root,tar) 函数
     * 递推参数：当前节点 root 当前目标值 tar
     * 终止条件：若节点root为空，则直接返回
     * 递推工作：
     * 1.路径更新：将当前节点 root.val 加入路径 path
     * 2.目标值更新：tar = tar - root.val （即目标值 tar 从 sum减到0）
     * 3.路径记录：当 root为叶节点 且 路径和等于目标值，则将此路径加入到 res
     * 4.先序遍历：递归左右子节点
     * 5.路径恢复：向上回溯，需要将当前节点从 路径path中删除，即执行 path.pop()
     *
     * @param root
     * @param target
     * @return
     */
    LinkedList<List<Integer>> res = new LinkedList<>();
    // 声明的类型 为 LinkedList 因为操作多为 插入删除
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        // 初始化：结果列表 res，路径列表 path

        // 开始递归
        recur(root, target);

        // 返回值
        return res;
    }

    public void recur(TreeNode root, int tar) {
        // 寻找递推的终止条件
        if (root == null) {
            return;
        }
        // 开始递推
//        1.路径更新：将当前节点 root.val 加入路径 path
        path.add(root.val);
//        2.目标值更新：tar = tar - root.val （即目标值 tar 从 sum减到0）
        tar = tar - root.val;
//        3.路径记录：当 root为叶节点 且 路径和等于目标值，则将此路径加入到 res
        if (tar == 0 && root.left == null && root.right == null) {
            // 注意：记录路径时若直接执行 res.add(path) 相当于将 path对象加入了res；后续 path改变时，res中的path对象也会随之改变
            // 正确做法：res.add(new LinkedList<>(path)) ，相当于复制了一个path并加入到了res
            res.add(new LinkedList<>(path));
        }
//        4.先序遍历：递归左右子节点
        recur(root.left, tar);
        recur(root.right, tar);
//        5.路径恢复：向上回溯，需要将当前节点从 路径path中删除，即执行 path.pop()
//        Removes and returns the last element from this list
        path.removeLast();
    }


    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
